package com.humngyang.com.hmy.study.shuzu;



public class Sort {
    /**
     * Description: 手动理解冒泡排序，原理在于每次遍历比较前一个值和后一个值的大小然后进行位置互换
     * Author: humingyang
     * Date: 2020/1/7 10:01
     */
    public static long[] bubblesort(long[] arr) {
        //设置一个临时变量赋值
        long tem = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            //第一次for循环之后，就能得到第一个最小的值，故只需要遍历后面的值就行
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[j] < arr[j - 1]) {
                    //j大于j-1的话，说明后面的数小于前面的数,将j和j-1转换赋值  1,4,2
                    tem = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = tem;
                }
            }
        }
        return arr;
    }

/**
 *   Description: 手撕直接排序，直接排序的原理在于一直找最小的值，然后交换位置,效率高于冒泡排序
 *   Author: humingyang
 *   Date: 2020/1/7 10:42
 *
 */
    public static long[] directselectsort(long[] arr) {
        long tem = 0;
        int k=0;
        for (int i = 0 ;i<arr.length-1;i++) {
            k=i;//第一遍将0赋予给k的值，默认第一个值最小
            for (int j = i; j <arr.length-1 ; j++) {//从第2个数字开始比较，依次与第一个数字进行，直到找到最小的值
                if (arr[k]>arr[j]){//如果k大于j的话，那么说明j已经值最小值了,只需要将j的值赋予k，k就是最小值
                    k=j;//将j的值赋予k的值，说明k已经是最小值，那么只需要比较k与i的值
                }
            }
            tem = arr[i];//将i的值赋予一个新的tem临时值,这个是大于k的值
            arr[i] = arr[k];//因为k=j的值小于i的值，所以将最小的值赋予第一次循环的i的值，就能够得到第一次循环之后得到的最小值
            arr[k] = tem;//然后将原本最小值的位置赋予大于原来最小的值。完成大值和小值的转换
        }
        return arr;
    }
    
    
    /**
     *   Description: 手撕直接插入排序，
     *   Author: humingyang
     *   Date: 2020/1/7 11:27
     */  

    public static long[] directinsertsort(long[] arr){

        long tem = 0;
        for (int i = 1;i<arr.length;i++) { //从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
            tem = arr[i]; //记录要插入的数据
            int j = i;
            while (j>0 && arr[j-1] >=tem){ // 从已经排序的序列最右边的开始比较(也就是从未排序的序列最左边开始)，找到比其小的数
                arr[j] = arr[j-1];  //向后挪动
                j--;//当前批次中循环移动
            }
            arr[j] = tem; //存在比其小的数，插入
        }
        return arr;
    }
    

      
     
      
     
      
     
     
     
     
    
     
    
    
    
    

}
